﻿#include"Maze.h"

void Setpos(int x, int y)
{
	COORD pos = { x,y };
	HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleCursorPosition(handle, pos);
}


void Maze::Stack::Push(TypeData x)
{
	if (_size + 1 >= _capacity)
	{
		int newcapacity = 2 * _capacity;
		TypeData* tmp = (TypeData*)realloc(_a, newcapacity*sizeof(TypeData));
		assert(tmp);
		_a = tmp;
		_capacity = newcapacity;
	}
	
	_a[++_size]._x = x._x;
	_a[_size]._y = x._y;
}

bool Maze::IsNodeTure(int x,int y)
{
	if (y >= 0 && y < _rows
		&& x >= 0 && x < _cols
		&& _pool[y][x] == 0)
	{
		return 1;
	}
	else
		return 0;
}

bool Maze::GetPassage(int x,int y)
{
	Node node(x, y);
	
	_stack.Push(node);

	if (x == _cols - 1 && y == 0)
	{
		if (_minstack.IsEmpity() || _minstack.GetSize() > _stack.GetSize())
		{
			_minstack = _stack;
		}
	}

	_pool[y][x] = -1;
	//up
	if (IsNodeTure(x,y - 1))
	{
		GetPassage(x, y - 1);

	}
	//down
	if (IsNodeTure(x,y + 1))
	{
		GetPassage(x, y + 1);

	}
	//left
	if (IsNodeTure(x - 1,y))
	{
		GetPassage(x - 1, y);

	}
	//right
	if (IsNodeTure(x + 1,y))
	{
		GetPassage(x + 1, y);

	}

	_stack.Pop();
	_pool[y][x] = 0;
	if (_minstack.IsEmpity())
		return 0;
	else
		return 1;
}

Maze::Stack& Maze::Stack::operator=(Maze::Stack& s)
{
	if (_a != nullptr)
	{
		free(_a);
		_a = nullptr;
	}
	int size = s.GetSize();
	_a = (TypeData*)malloc(sizeof(TypeData) * s.GetCapacity());
	assert(_a);
	_size = size;
	_capacity = s.GetCapacity();
	for (int i = 0; i <= size; i++)
	{
		_a[i]._x = s._a[i]._x;
		_a[i]._y = s._a[i]._y;
	}
	return *this;
}

void Maze::Print_Passage()
{
	Stack newstack, oldstack = _minstack;
	while (!oldstack.IsEmpity())
	{
		newstack.Push(oldstack.Top());
		oldstack.Pop();
	}
	int i = 5;
	while (!newstack.IsEmpity())
	{
		i--;
		printf("(%d,%d)->", newstack.Top()._x, newstack.Top()._y);
		newstack.Pop();
		if (!i)
		{
			std::cout << std::endl;
			i = 5;
		}
	}
	std::cout << "win";
}

Maze::Maze()
{
	cin >> _rows >> _cols;
	_pool = (int**)malloc(sizeof(int*) * _rows);
	assert(_pool);
	for (int i = 0; i < _rows; i++)
	{
		_pool[i] = (int*)malloc(sizeof(int) * _cols);
		assert(_pool[i]);
	}

	for (int i = 0; i < _rows; i++)
	{
		for (int j = 0; j < _cols; j++)
		{
			cin >> _pool[i][j];
		}
	}
	_node._x = _node._y = 0;
}


void Init(int** pool, const int* a,int len)
{
	for (int i = 0; i < len; i++)
	{
		(*pool)[i] = a[i];
	}
}

Maze::Maze(int)
	:_rows(6)
	,_cols(6)
	,_x(2)
	,_y(0)
	,_dir(0)
{
	_pool = (int**)malloc(sizeof(int*) * _rows);
	assert(_pool);
	for (int i = 0; i < _rows; i++)
	{
		_pool[i] = (int*)malloc(sizeof(int) * _cols);
		assert(_pool[i]);
	}

	int a1[] = { 0,-2,0,0,1,0 };
	int a2[] = { 1,1,0,2,2,0 };
	int a3[] = { 1,0,0,0,1,0 };
	int a4[] = { 0,2,1,2,1,0 };
	int a5[] = { 0,0,1,0,1,0 };
	int a6[] = { 0,0,0,0,0,0 };

	Init(&_pool[0], a1, 6);
	Init(&_pool[1], a2, 6);
	Init(&_pool[2], a3, 6);
	Init(&_pool[3], a4, 6);
	Init(&_pool[4], a5, 6);
	Init(&_pool[5], a6, 6);
}

void Maze::Walk()
{
	int i = 0;
	int x = _x, y = _y;
	if (KEY_PRESS(VK_RIGHT))
	{
		_dir = RIGHT;
		if (_x < _cols * 2 - 2 && _pool[_y][_x / 2 + 1] == 0)
		{
			i++;
			_x += 2;
		}
		
	}
	else if (KEY_PRESS(VK_LEFT))
	{
		_dir = LEFT;
		if (_x > 0 && _pool[_y][_x / 2 - 1] == 0)
		{
			i++;
			_x -= 2;
		}
	}
	else if (KEY_PRESS(VK_UP))
	{
		_dir = UP;
		if (_y > 0 && _pool[_y - 1][_x / 2] == 0)
		{
			i++;
			_y -= 1;
		}
	}
	else if (KEY_PRESS(VK_DOWN) )
	{
		_dir = DOWN;
		if (_y < _rows - 1 && _pool[_y + 1][_x / 2] == 0)
		{
			i++;
			_y += 1;
		}
	}

	if (i)
	{
		Setpos(x + 2, y + 1);
		std::cout << "  ";
		_pool[y][x / 2] = 0;

		Setpos(_x + 2, _y + 1);
		std::cout << "●";
		_pool[_y][_x / 2] = -2;

	}
}

void Maze::Nudeg()
{

	if (KEY_PRESS(VK_F1))
	{
		int i = 0, x1 = 0, y1 = 0, x2 = 0, y2 = 0;
		if (_dir == UP && _y - 1 >= 0 && _pool[_y - 1][_x / 2] == 2
			&& _y - 2 >= 0 && _pool[_y - 2][_x / 2] == 0)
		{
			i++;
			y1 = _y - 1, x1 = _x / 2;
			y2 = _y - 2, x2 = _x / 2;
		}
		else if (_dir == DOWN && _y + 1 < _rows && _pool[_y + 1][_x / 2] == 2
			&& _y + 2 < _rows && _pool[_y + 2][_x / 2] == 0)
		{
			i++;
			y1 = _y + 1, x1 = _x / 2;
			y2 = _y + 2, x2 = _x / 2;
		}
		else if (_dir == LEFT && _x - 2 >= 0 && _pool[_y][_x / 2 - 1] == 2
			&& _x - 4 >= 0 && _pool[_y][_x / 2 - 2] == 0)
		{
			i++;
			y1 = _y, x1 = _x / 2 - 1;
			y2 = _y, x2 = _x / 2 - 2;
		}
		else if (_dir == RIGHT && _x + 2 <= _cols * 2&& _pool[_y][_x / 2 + 1] == 2
			&& _x + 4 <= _cols * 2 && _pool[_y][_x / 2 + 2] == 0)
		{
			i++;
			y1 = _y, x1 = _x / 2 + 1;
			y2 = _y, x2 = _x / 2 + 2;
		}
		if (i)
		{
			swap(_pool[y1][x1], _pool[y2][x2]);
			Setpos(x1 * 2 + 2, y1 + 1);
			std::cout << "  ";
			Setpos(x2 * 2 + 2, y2 + 1);
			std::cout << "□";
		}
	}
}

void Maze::screen()
{
	Setpos(0, 0);
	std::cout << " +------------+";
	for (int i = 0; i < _rows; i++)
	{
		Setpos(0, i + 1);
		std::cout << " |";
		for (int j = 0; j < _cols; j++)
		{
			if (_pool[i][j] == 1)
			{
				std::cout << "○";
			}
			else if (_pool[i][j] == 2)
			{
				std::cout << "□";
			}
			else
			{
				std::cout << "  ";
			}
		}
		std::cout << "|";
	}
	std::cout << std::endl << " +------------+";
}

int Maze::Game()
{
	screen();
	Setpos(_x, _y + 1);
	std::cout << "萤●";
	Setpos(_cols * 2, 1);
	std::cout << "花";
	while (1)
	{
		Setpos(0, _rows + 4);
		std::cout << "当前方向为：";
		if (_dir == UP)
			std::cout << "↑";
		else if (_dir == DOWN)
			std::cout << "↓";
		else if (_dir == LEFT)
			std::cout << "←";
		else if (_dir == RIGHT)
			std::cout << "→";

		else if (KEY_PRESS(VK_ESCAPE))
		{
			break;
		}
		Walk();
		Nudeg();
		if (GetPassage())
		{
			Setpos(0, _cols + 5);
			std::cout << "###  解题正确  ###" << std::endl;
			std::cout << "## 方案路径如下 ## (x,y)" << std::endl;
			Print_Passage();
			return 1;
		}




	}
	return 0;
}

